package tree.traversal;

import tree.TreeNode;

import java.util.Stack;

/**
 * @author justnow
 * Created on 2020-09-07
 * Description
 */
public class PostOrder {

    //后序遍历实现方法二:双栈法
    public void PostOrderTraverse2(TreeNode pNode)
    {
        if(pNode == null)
            return ;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();//辅助栈
        //存入根节点，初始化
        stack1.push(pNode);
        //stack1弹出的元素，压入stack2，在将该元素的左右节点压入stack1
        while(!stack1.isEmpty())
        {
            pNode = stack1.pop();
            stack2.push(pNode);
            if(pNode.left != null)
            {
                stack1.push(pNode.left);
            }
            if(pNode.right != null)
            {
                stack1.push(pNode.right);
            }
        }

        //stack弹出的即是后序遍历的顺序
        while(!stack2.isEmpty())
        {
            System.out.print(stack2.pop().val + " ");
        }

    }

}
